package Leetcode100Hot;

import java.util.*;

/*
路径总和 III
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例 1：
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。
示例 2：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3

提示:
二叉树的节点个数的范围是 [0,1000]
-109 <= Node.val <= 109
-1000 <= targetSum <= 1000
 */
public class _31路径总和3 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    //DFS
    //WA  对象数值溢出问题  128/129
    //ps : AC  将int 改成 long 就可以AC
    //ps2 : 2^31 - 1 大约等于 2 * 10^9
    int count = 0;

    public int pathSum(TreeNode root, int targetSum) {
        dfs(root, targetSum);
        return count;
    }

    public ArrayList<Long> dfs(TreeNode root,int target) {
        if (root == null) {
            return new ArrayList<>();
        }
        ArrayList<Long> list = new ArrayList<>();
        if (root.val == target){
            count++;
        }
        list.add((long)root.val);
        ArrayList<Long> dfs1 = dfs(root.left,target);
        ArrayList<Long> dfs2 = dfs(root.right,target);
        for (Long i : dfs1) {
            long num = root.val + i;
            if (num == target) {
                count++;
            }
            list.add(num);
        }
        for (Long i : dfs2) {
            long num = root.val + i;
            if (num == target) {
                count++;
            }
            list.add(num);
        }
        return list;
    }

    //官解：方法一：深度优先搜索
    /*
    作者：力扣官方题解
    链接：https://leetcode.cn/problems/path-sum-iii/solutions/1021296/lu-jing-zong-he-iii-by-leetcode-solution-z9td/
     */
    class Solution {
        public int pathSum(TreeNode root, long targetSum) {
            if (root == null) {
                return 0;
            }

            int ret = rootSum(root, targetSum);
            ret += pathSum(root.left, targetSum);
            ret += pathSum(root.right, targetSum);
            return ret;
        }

        public int rootSum(TreeNode root, long targetSum) {
            int ret = 0;

            if (root == null) {
                return 0;
            }
            int val = root.val;
            if (val == targetSum) {
                ret++;
            }

            ret += rootSum(root.left, targetSum - val);
            ret += rootSum(root.right, targetSum - val);
            return ret;
        }
    }

    //官解：方法二：前缀和
    /*
    作者：力扣官方题解
    链接：https://leetcode.cn/problems/path-sum-iii/solutions/1021296/lu-jing-zong-he-iii-by-leetcode-solution-z9td/
     */
    class Solution2 {
        public int pathSum(TreeNode root, int targetSum) {
            Map<Long, Integer> prefix = new HashMap<Long, Integer>();
            prefix.put(0L, 1);
            return dfs(root, prefix, 0, targetSum);
        }

        public int dfs(TreeNode root, Map<Long, Integer> prefix, long curr, int targetSum) {
            if (root == null) {
                return 0;
            }

            int ret = 0;
            curr += root.val;

            ret = prefix.getOrDefault(curr - targetSum, 0);
            prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);
            ret += dfs(root.left, prefix, curr, targetSum);
            ret += dfs(root.right, prefix, curr, targetSum);
            prefix.put(curr, prefix.getOrDefault(curr, 0) - 1);

            return ret;
        }
    }

}
